//
// Created by Lenovo on 2024/2/1.
//
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    //求摆动序列最长子序列的长度
    int wiggleMaxLength(vector<int>& nums) {
        int dp[1010][2];                            //dp[i][0]：表示考虑前i个数，且第i个数为山峰的最长摆动序列的长度
        memset(dp,0,sizeof dp);       //dp[i][1]：表示考虑前i个数，且其i个数为山谷的最长摆动序列的长度
        dp[0][0]=1;                                 //初始化为1
        dp[0][1]=1;
        for(int i=1;i<nums.size();i++){
            dp[i][0]=dp[i][1]=1;                    //初始化
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){                        //i大，为山峰
                    dp[i][0]=max(dp[i][0],dp[j][1]+1);      //状态转移
                }else if(nums[j]>nums[i]){                  //i小，为山谷
                    dp[i][1]=max(dp[i][1],dp[j][0]+1);      //状态转移
                }
            }
        }
        return max(dp[nums.size()-1][0],dp[nums.size()-1][1]);
    }
};